Skip to main content

B-Tree Basic

B-trees are widely used in database storage engines and indexes. Their balanced shape keeps searches short even for large datasets, reducing the number of disk input/output (I/O) operations needed to find data.

Structure​

A B-tree stores sorted keys in pages. The root page is the entry point; internal pages point toward smaller key ranges; leaf pages hold the final key-to-value entries. Every leaf sits at the same depth, so no lookup takes a much longer path than another.

For example, a root containing separators M and T directs a search for R to the middle child, which contains only keys from M up to T.

Each Internal Node contain a N Keys (a.k.a index-entries,separator-key or dividir cells) and N+1 Pointers, being the +1 a point to the next Internal Node Leaf Nodes should always be at the same depth in B-Tree to prevent Tree getting unbalanced

The Tree is divided by Index Entries or Separator-Key or Divider Cells. These Keys splits the tree into smaller sub-trees - which holds a certain subrange of keys K1 < 1 < K3

B-Trees are organized into pages (2kb to 16kb - or a page from disk which may change from OS & Storage combo). The term Node is interchangeable with Page

Occupancy is how full a page is. Fan-out is the number of child pages an internal page can point to; high fan-out keeps the tree short.

A B-Tree delivers two essential assumptions about the data-structure:

  • High Fanout: which just means it grows horizontally - ie adding more internal nodes and just splitting/merging by necessity
  • Low Height: We only have 3 levels root, internal and leaf.

Algorithms​

B-Tree Insert Algorithm​

  • Perform B-Tree lookup to find Leaf Node and locate an insert point
  • Append the key and the value to the leaf node insertion point.
    • Updates only change the value.
  • In case of overflowed leaf nodes, ie exceeded maximum capacity, we split the leaf node
    • Split int case leaf node N+1 is reached
    • for Internal Nodes (N+1)+1 is reached.
B-Tree Insert (Splits) Promoted​

A insert is done by allocating a new node and transferring half of the keys and values into it. Then adding it's first key and point to the parent node. Being split point the index where we split the data, we transfer data from split point++ into the new node. If needed, we'll propagate the splits up above.

B-Tree Lookup Algorithm​

  1. From root node
  2. Perform BST comparing the searched KEY within the keys stored in Internal Nodes
  3. Find the first separator-key
  4. Access the InternalNode.subtree from that `separator-key
    1. Repeat the process of looking for equal separator-key until you reach a leaf-node
    2. If there's no key equal to your searched key and the left-most is lower, there's no key in your B-Tree

B-Tree and Disk Drives:​

Hard disk drives (HDDs) use a moving mechanical head. A disk seek moves that head to the right location before reading sectors, so scattered reads cost much more than adjacent reads. Typical range of bytes read in each sector - 512bytes to 4kb

Solid-state drives (SSDs) store data in flash cells grouped into pages and erase blocks. They read and write pages, but must erase an entire block before rewriting used space. A Block usually has 64 to 512 pages. The smallest unit for a SSD is a page. (2kb to 16kb). HOWEVER writing can only occur in empty blocks - ie we cannot update data. So we need to empty a block (delete it) - which can only occur by erase block. Unlike an HDD, an SSD has no moving head. Its flash translation layer (FTL) maps logical page addresses to physical flash locations and manages wear and cleanup. Responsabilities from FTL:

  • garbage collection
  • Mapping page ids to location in-disk
  • Tracking
    • empty pages
    • written pages
    • discarded pages

Differences between SSD and HDD​

Operating systems expose storage as block devices, which read and write fixed-size chunks. Sequential I/O accesses nearby chunks in order, avoiding repeated seeks; it is especially beneficial on HDDs.

Share: